package 三指针法_三路快排;

import com.alibaba.fastjson.JSON;

public class No75颜色分类 {

    /**
     * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，
     * 使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     * 注意:
     * 不能使用代码库中的排序函数来解决这道题。
     * 示例:
     * 输入: [2,0,2,1,1,0]
     * 输出: [0,0,1,1,2,2]
     */

    //采用三路快排
    public static void sortColors(int[] nums) {

        int zero=-1;//从0->zero这个区域的值为0
        //因为two会减小,所以剩下的就是1
        int two=nums.length;//从two->n-1这个区域是2

        for (int i = 0; i < two;) {
            if(nums[i]==1)//就不管它,继续往下移
                i++;
            else if(nums[i]==2){
                two--;
                int swap=nums[i];
                nums[i]=nums[two];
                nums[two]=swap;
            }else{//等于0就不管它
                zero++;
                int swap=nums[zero];
                nums[zero]=nums[i];
                nums[i]=swap;//当前i等于0了
                i++;//因为当前i已经是0,所以不需要再进行检测了,就++
            }
        }
    }

    public static void main(String[] args) {
        int[] arr=new int[]{2,0,2,1,1,0};
        sortColors(arr);
        System.out.println(JSON.toJSONString(arr));
    }

}
